Skip to content

Computation and Complexity

Efficient Algorithms

Run in time bounded by a polynomial in the input size

  1. Closed under composition

    We can use efficient solutions to subproblems in an efficient algorithm and still obtain an efficient algorithm

    Cobham Polynomial time functions are the smallest set of functions tat

    • Include all \(O(n)\)-time functions
    • Are closed under composition
    • Edmonds Polynomial time algorithms, in contrast to brute force enumerate-and-check. Use some structure of the problem

    In practice, subsequent work was always able to use these properties to obtain practically useful algorithms.

  2. Computing architecture changes

    Running times of algorithms may vary by a polynomial amount. It’s always possible to simulate one architecture by another with (only) a polynomial slowdown

    Thus, polynomial time is again the most conservative set of problems/algorithms that is the same across all architectures.

We’re interested in solving problem involing our knowledge representation

  1. The evaluation problem

    Given a representation of a property \(c\in\lbrace 0,1\rbrace ^n\) and a possible world \(\bar x\in \lbrace 0,1\rbrace ^n\)

    Return: if \(\bar x\in c\) or not

    When there is a polynomial-time algorithm for the evaluation problem, the family is efficiently evaluable.

  2. The satisfiability problem

    Given a representation of a property \(c\)

    Return: if \(\bar x\in c\) or none

There is an efficient algorithm for satisfiability problem of conjunctions

Scan conjunction, set corresponding value (that would satisfy the current literal) in the possible world unless the value was already set (then return 1). Set the remaining attributes not mentioned to 0.

At the end, all of the literals of the conjunction are set true, runs in linear time.

Problems

Satifiability Problem

Finding a world that returns true for the given constraints

Relation Problem

For set \(X\) (input) and \(Y\) (output) a relations \(R\subseteq X\cdot Y\)

Goal given \(x\in X\), find, \(y\in Y\), such that \((x,y)\in R\)

NP-Search Problem

It is a relational problem \(R\), which the followings are true

  • \(R\) is polynomially balanced

    There exists a polynomial \(p(|x|)\) such that if \((x,y)\in R\) there is also a \(y'\in p(|x|)\) such that \((x,y')\in R\). (The confusing version)

    There existing a polynomial \(p(|x|)\) such that, for all \(y\) that \((x,y)\in R\), \(|y|\leq p(|x|)\). (The better version)

  • \(R\) is efficient verifiable

    There is an algorithm \(A\) for computing the relation such that \(A(x,y)\) returns true if \((x,y)\in R\). Otherwise in polynomial \((O(x,y))\)

e.g., satisfiability problem for conjunction

Polynomial Reduction

Given a relation problem \(P\), we say \(P\) polynomially-time reduction to a relation problem \(Q\), if there is an algorithm for \(P\) that is polynomial when given information from the solution to \(Q\) (run \(Q\) polynomially). REFER TO CSE 347/3407

NP-Complete

A relation problem \(P\) is NP complete if every NP-search problem \(R\) poly-time reduction to \(P\). REFER TO CSE 347/3407

Note

Suppose we have a poly-time reduction from a NP-complete problem \(P\) to NP-search problem \(R\), then \(R\) is NP-complete.

Cook-Levin; the 3SAT problem

Boolean Circuit

A Boolean circuit is given a directed acyclic graph with \(n\) starting nodes and \(k\) sinks (\(f:\lbrace 0,1\rbrace ^n\rightarrow\lbrace 0,1\rbrace ^k\)) . The starting nodes, \(X_i\), the ending nodes, \(Y_i\), and interior nodes \(\land,\lor,\lnot\).

Proposition—Proof 3.6

Suppose there is a poly-time algorithm solving $\bigcup_{n\in N}\lbrace (x,y),f_n(x)=y,\lbrace 0,1\rbrace ^n\rightarrow\lbrace 0,1\rbrace ^{k(n)}\rbrace $

There is another poly-time algorithm \(PRINT_f\) that has input \(n\), and outputs a Boolean circuit computing \(f_n(x)\)

Circuit SAT

Given a Boolean circuit and output \(y\), find a set \(x\) value that results in \(y\).

This is NP-complete

  • Proof

    Let S ⊆ 0, 1 × 0, 1 be any NP-search problem. Then there exists a polynomial p and a polynomial-time verifier V such that (x, y) ∈ S ⇔ V(x, y) = 1  and  |y| ≤ p(|x|).

    Padding to fixed witness length. Define S′ by (x, y′) ∈ S′ ⇔ ∃y: (x, y) ∈ S and y′ = y, 0, p(|x|) − |y|. Then |y′| = p(|x|), and from any valid y′ for S′ we can recover a valid witness y for S by deleting trailing zeros. Hence it suffices to reduce S′ to Circuit-SAT Search.

    Reduction. Fix an instance x, and let m := p(|x|). Define the Boolean function fx(y′) := V′(x, y′)  for y′ ∈ 0, 1m. Since V′ runs in polynomial time, we can construct (by unrolling the computation of V′) in polynomial time a Boolean circuit Cx of size poly(|x|) such that for all y′ ∈ 0, 1m, Cx(y′) = V′(x, y′). Output the Circuit-SAT Search instance (Cx, 1).

    Correctness.

    • If (x, y′) ∈ S′, then V′(x, y′) = 1, so C(y′) = 1, hence y′ is a satisfying assignment for (C, 1).
    • If Circuit-SAT Search returns y′ with C(y′) = 1, then V′(x, y′) = 1, so (x, y′) ∈ S′, and stripping padding yields a witness for S.

    Thus every NP-search problem reduces to Circuit-SAT Search in polynomial time, so Circuit-SAT Search is NP-hard. It is also in NP-search (verify C(a) = 1 in polynomial time). Therefore Circuit-SAT Search is NP-complete.